package com.lsa.iview.heaps;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import junit.framework.TestCase;

import com.lsa.helpers.IntegerComparator;
import com.lsa.helpers.Utils;

public class TestHeap extends TestCase {
	public void test(){
		Heap<Integer> h = new Heap<>(IntegerComparator.instance());
		
		List<Integer> elems = Arrays.asList(15, 12, 13, 7, 25, 3, 2, 1);
		for (int i = 0; i < elems.size(); i++) {
			h.insert(elems.get(i));
		}
		assertEquals(elems.size(), h.size());
		Collections.sort(elems, Collections.reverseOrder());

		for (int i = 0; i < elems.size(); i++) {
			assertEquals(elems.get(i), h.extractHead());
			assertEquals(elems.size() - i - 1, h.size());
		}
		
		h = new Heap<>(elems.toArray(new Integer[0]), IntegerComparator.instance());
		for (int i = 0; i < elems.size(); i++) {
			assertEquals(elems.get(i), h.extractHead());
			assertEquals(elems.size() - i - 1, h.size());
		}
		
		h = new Heap<>(elems.toArray(new Integer[0]), IntegerComparator.instance());
	}

	public void testPriorityQueue(){
		PriorityQueue<Key> h = new PriorityQueue<>(new Comparator<Key>(){
			@Override
			public int compare(Key o1, Key o2) {
				return o2.key - o1.key;
			}
		});
		
		List<Integer> elems = Arrays.asList(15, 12, 13, 7, 25, 3, 2, 1);
		for (int i = 0; i < elems.size(); i++) {
			h.insert(new Key(elems.get(i), elems.get(i)));
		}
		
		Collections.sort(elems);
		for (int i = 0; i < elems.size(); i++) {
			Key extractedHead = h.extractHead();
			assertEquals((Integer)elems.get(i), (Integer)extractedHead.value);
			assertEquals(elems.size() - i - 1, h.size());
		}
		
		elems = Arrays.asList(15, 12, 13, 7, 25, 3, 2, 1);
		for (int i = 0; i < elems.size(); i++) {
			Key key = new Key(elems.get(i), elems.get(i));
			h.insert(key);
		}
		h.updateKey(new Key(0, elems.get(0)));
		
		elems.set(0, 0);
		Collections.sort(elems);
		
		{
			Key extractedHead = h.extractHead();
			assertEquals((Integer)15, (Integer)extractedHead.value);
			assertEquals((Integer)0, (Integer)extractedHead.key);
		}
		
		for (int i = 1; i < elems.size(); i++) {
			Key extractedHead = h.extractHead();
//			System.out.println(extractedHead);
			assertEquals((Integer)elems.get(i), (Integer)extractedHead.value);
			assertEquals(elems.size() - i - 1, h.size());
		}
	}
	
	public void testPriorityQueue2(){
		PriorityQueue<Key> h = new PriorityQueue<>(new Comparator<Key>(){
			@Override
			public int compare(Key o1, Key o2) {
				return o2.key - o1.key;
			}
		});

		for (int i = 1; i < 101; i++) {
			h.insert(new Key(i, i+ 100));
		}
		
		h.updateKey(new Key(-1, 150));
		h.updateKey(new Key(-2, 151));
		
		List<Integer> keys = new ArrayList<>();
		List<Integer> values = new ArrayList<>();
		
		keys.add(-2);
		keys.add(-1);
		
		values.add(151);
		values.add(150);
		
		keys.addAll(Utils.createIntegerListUniform(1, 49, 1));
		keys.addAll(Utils.createIntegerListUniform(52, 100, 1));
		
		values.addAll(Utils.createIntegerListUniform(101, 149, 1));
		values.addAll(Utils.createIntegerListUniform(152, 200, 1));
		
		int i = 0;
		
		while(h.size() > 0) {
			Key extractedHead = h.extractHead();
			assertEquals((Integer)keys.get(i), (Integer)extractedHead.key);
			assertEquals((Integer)values.get(i), (Integer)extractedHead.value);
			++i;
		}
	}
	
	/**
	 * @author lsa80
	 *
	 */
	private static class Key{
		int key;
		int value;
		
		public Key(int key, int value) {
			this.key = key;
			this.value = value;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + value;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			Key other = (Key) obj;
			if (value != other.value)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return "Key [key=" + key + ", value=" + value + "]";
		}
	}
}
